package arrangeCoins;

public class Solution {
    public int arrangeCoins(int n) {
//        int k=1;
//        while(true){
//            if(((k+1)*k/2)>n){
//                return k-1;
//            }
//            k++;
//        }
        int l=1;
        int r=n;
        int mid=1;
        while(l<r){
            mid=l+(r-l)/2;

            int k=(mid+1)*mid/2;

            int rest=n-k;//剩下的那一行的数据，如果0<=rest<mid+1，return mid
            if(rest<0){
                r=mid;
            }else if(rest<mid+1){
                return mid;
            }else{
                l=mid;
            }
        }
        return mid;
    }
    // 完整的k行阶梯需要的数字n==(k+1)*k/2
    // 第k行有k个
    // 1
    // 2 3
    // 4 5 6
    // 7 8 9 10
    // 11

//        public int arrangeCoins(int n) {
//            return (int) ((Math.sqrt((long) 8 * n + 1) - 1) / 2);
//        }求解方程 (x+1)*x/2==n
//    public int arrangeCoins(int n) {
//        int left = 1, right = n;
//        while (left < right) {
//            int mid = (right - left + 1) / 2 + left;
//            if ((long) mid * (mid + 1) <= (long) 2 * n) {
//                left = mid;
//            } else {
//                right = mid - 1;
//            }
//        }
//        return left;
//    } 二分查找

}
